package base;

import java.awt.geom.Line2D;
import java.awt.geom.Path2D;
import java.awt.geom.Point2D;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.logging.Level;
import java.util.logging.Logger;


/**
 * In the end, this class should answer to question "which parts of these given ships does this turret see?"
 * TODO: We still need to find out how we formulate "parts of a ship"..
 * 
 * 
 * 
 * Optimointeja:
 *  - koko homman voisi pistää uusiksi käyttäen jotain "polygon visibility"-algoritmin varianttia
 *  - turrettien toimintaa voisi hoitaa esim. neljännessekunnin välein, jolloin ensin laskettaisiin ja talletettaisiin kaikille aluksille
 *  lokaatiot, jolloin näitä (ja niihin liittyviä trigonometriaa) ei tarvitsisi laskea kuin kerran. tämä pitää kuitenkin tehdä korkeammalla tasolla
 *  
 * @author gilead
 *
 */
public /*abstract*/ class Visibility implements Serializable {
	/**
	 * 
	 */
	private static final long serialVersionUID = -6491482478501662947L;

	/**
	 * 
	 */
	//private static final long serialVersionUID = 1L;
	
	/** The {@link Logger} for this class. */
    private static final Logger logger =
        Logger.getLogger(Visibility.class.getName());
	
    /**
     * Creates and returns a ship silhouette of the given ship s, assuming the ship is at least partially in the given arc,
     * and at least one corner points of the ship is within the given distance.
     * 
     * If the ship fills the arc fully, the returned silhouette is the whole arc. 
     * 
     * If none of the angles to ship from turret are within given arc, returns null.
     * 
     * If none of the corner points of the given ship are within rangelimit, returns null.
     * 
     * NOTE: it is not guaranteed (or calculated) if the whole arc of the silhouette is within rangeLimit,
     *       only that at least one corner point is.
     * 
     * @param s the ship we're creating a silhouette of
     * @param turret the location of the point we're watching from (the origo)
     * @param minDistSq the distance at least one of the corner points of the ship must fall in, squared
     * @param turretArc the arc that we're watching
     * @return
     */
    public static ShipSilhouette generateShipSilhouette(Ship s, Point2D.Double turret, Arc turretArc, double minDistSq)
	{
    	if (s == null) {
    		logger.log(Level.INFO, "the given target ship was null");
    		return null;
    	}
		Point2D.Double [] corners = s.getRect();
		
		double[] cornerAngles = new double[4];
		double[] distSquared = new double[4];
		
		for (int i = 0; i < 4; i++)
		{
			cornerAngles[i] = Geometry.getHeading(turret.x, turret.y, corners[i].x, corners[i].y);
			distSquared[i] = Geometry.getDistanceSquared(turret.x, turret.y, corners[i].x, corners[i].y);
		}
		
		// check if any of the corner points are within range
		
		boolean someWithinRange = false;
		for (int i = 0; i < 4; i++)
		{
			if (distSquared[i] <= minDistSq)
			{
				someWithinRange = true;
				break;
			}
		}
		if (someWithinRange == false) {
			// if none of the corner points are within range..
			logger.log(Level.FINEST, "none of the corner within range");
			return null;
		}
		
		// rest is figuring out if the ship crosses the positive x-axle
		
		Point2D.Double [] relative = new Point2D.Double[4];
		
		for (int i=0; i < 4; i++) {
			relative[i] = new Point2D.Double(corners[i].x - turret.x, corners[i].y - turret.y);
		}
		
		boolean crosses360line = false;
		
		for (int i=0; i < 4; i++) {
			if (relative[i].x > 0 && relative[i].y > 0) {
				// the corner is in NE quadrant
				int nextIndex = Ship.getNextIndex(i);
				
				if (relative[nextIndex].y < 0) {
					// the next point is either in SE or SW quadrant, i.e. the line cross the x-axle
					
					if (Geometry.solveXforLine(relative[i], relative[nextIndex], 0) > 0)
					{
						// the line goes over the positive y-axle
						crosses360line = true;
						// no need to continue further
						break;
					}
				}
			}
		} 
		
		int beginIndex = -1, endIndex = -1;
		
		if (crosses360line) {
			for(int i=0; i < 4;i++)
			{
				if(relative[i].y < 0)
				{
					if (beginIndex == -1)
					{
						beginIndex = i;
					}
					// amongst the points below the x-axle..
					// search for the smallest angle
					else if (cornerAngles[i] < cornerAngles[beginIndex])
					{
						beginIndex = i;
					}
				}
				else
				{
					if (endIndex == -1)
					{
						endIndex = i;
					}
					// amongst the points above the x-axle..
					// search for the biggest angle
					else if (cornerAngles[i] > cornerAngles[endIndex])
					{
						endIndex = i;
					}
				}
			}
			logger.log(Level.FINEST, "ship goes over the 360 line"); 
		}
		else
		{
			beginIndex = Visibility.getMinIndex(cornerAngles);
			endIndex = Visibility.getMaxIndex(cornerAngles);
			logger.log(Level.FINEST, "ship doesn't go over the 360 line");
		}
		
		Arc arc = new Arc(cornerAngles[beginIndex], cornerAngles[endIndex]);
		
		arc = arc.intersect(turretArc);
		
		if (arc == null)
		{
			return null;
		}
		
		return new ShipSilhouette(s, arc, corners[beginIndex], corners[endIndex], distSquared); 
	}
    
    /**
     * Returns the index of the smallest number in the given array.
     * 
     * @param numbers
     * @return
     */
    protected static int getMinIndex(double numbers [])
    {
    	int result = 0;
    	
    	for (int i=1; i < numbers.length; i++) {
    		if (numbers[i] < numbers[result]) {
    			result = i;
    		}
    	}
    	return result;
    }
    
    /**
     * Returns the index of the biggest number in the given array.
     * 
     * @param numbers
     * @return
     */
    protected static int getMaxIndex(double numbers [])
    {
    	int result = 0;
    	
    	for (int i=1; i < numbers.length; i++) {
    		if (numbers[i] > numbers[result]) {
    			result = i;
    		}
    	}
    	return result;
    }
    
    /**
     * If a line that is not blocked by other ships exists from the given turret to the given target ship, this function 
     * returns the angle from the turret to the ship. If no such line exists, this function returns Double.NaN.
     * 
     * This function goes through all possibly blocking ships and checks if they block the line to the target ship.
     * 
     * @param targetShip ship we're aiming at
     * @param turret turret we're aiming from. we search for the angle only in this turret's firing arc
     * @return angle from the turret to the target ship, or NaN if no unobstructed line exists.
     */
    public double getFiringAngle(Ship targetShip, Ship shootingShip, Turret turret)
	{
		Point2D.Double turretPos = turret.getPos(); 
		
		ShipSilhouette target = Visibility.generateShipSilhouette(targetShip, turretPos, turret.getArc(), turret.getOptimal() * turret.getOptimal());
		
		if (target == null) {
			// the target is not within turret's reach
			return Double.NaN;
		}
		
		// we'll need the distances when doing ship-by-ship silhouette blocking
		double minDistSq = target.getMinDistanceSq();
		
		ArrayList<Arc> anglesToTarget = getAnglesToTarget(target, turretPos, shootingShip, minDistSq);
		
    	if (anglesToTarget.isEmpty()) {
    		return Double.NaN;
    	}
    	
    	Iterator <Arc> itr = anglesToTarget.iterator();
    	while (itr.hasNext()) {
    		Arc current = itr.next();
    		logger.log(Level.FINEST, "We see the target from {0} to {1}", new Object[]{current.beginAngle, current.endAngle});
    	}
    	
		// TODO: we still should check if the turret's optimal reduces the silhouette
		
    	Arc angle = anglesToTarget.get(0); 
		return angle.getMiddleAngle();
	}
		
	/**
	 * Combines Arcs that overlap into single Arcs, and returns that list.
	 * Assumes that given Arcs are sorted by their beginning angles in clockwise order.
	 * 
	 * for example, these lists of beginning angles are sorted:
	 *  50, 60, 300
	 *  300, 50, 60
	 * 
	 * and this is not:
	 * 60, 50, 300
	 *  
	 * 
	 * @param arcs list of Arcs, assumed sorted by the beginningAngle
	 */
	public static ArrayList<Arc> combineContinousArcs(ArrayList<Arc> arcs)
	{
		ArrayList<Arc> result = new ArrayList<Arc> (); 
		
		Iterator <Arc> itr = arcs.iterator();
		
		if (!itr.hasNext()) {
			// the given list was empty, we return an empty list
			return result;
		}
		Arc earlier = itr.next(), current;
		result.add(earlier);
		
		while (itr.hasNext()) {
			current = itr.next();
			
			if (earlier.contains(current)) {
				// the arc won't be added to the result list
				continue;
			}
			if (current.contains(earlier)) {
				result.remove(result.size()-1); // remove the earlier from results
				earlier = new Arc(current);
				result.add(earlier);
			}
			if (earlier.overlaps(current)) {
				result.remove(result.size()-1); // remove the earlier from results
				earlier = earlier.combine(current); //new Arc(earlier.beginAngle, current.endAngle);
				result.add(earlier);
			}
			else
			{
				result.add(current);
				earlier = current;
			}
		}
		
		return result;
	}
	
	/**
	 * Returns a list of arcs from the shooting ship into target silhouette that are not blocked by other ships in the ship list.
	 * Basically checks if the target silhouette is fully blocked by other ships, or if there are holes through which it can be seen.   
	 * 
	 * @param target the silhouette we are aiming at
	 * @param turret the location of the turret that is shooting
	 * @param shootingShip the ship that the shooting turret is attached to
	 * @param minDistSq distance our turret can shoot to, squared
	 * @return
	 */
	public ArrayList<Arc> getAnglesToTarget(ShipSilhouette target, Point2D.Double turret, Ship shootingShip, double minDistSq) {
		ArrayList<ShipSilhouette> blockedAngles = getBlockingSilhuettes(target, turret, shootingShip, minDistSq);
		
		// arc from turret to the target ship that hasn't been blocked yet
		// gets cut smaller in the loop by the blocking silhouettes
		Arc limit = new Arc(target.fromTurret);
		
		// now we have the blocked angles in a list.. let's see how much we've still got left  
    	ArrayList<Arc> anglesToTarget = new ArrayList<Arc> ();
    	
    	if (blockedAngles.isEmpty())
		{
    		if (limit != null)
    		{
    			anglesToTarget.add(limit);
    		}
			return anglesToTarget;
		}
    	
    	// sort the blocked list
    	Collections.sort(blockedAngles, new ShipSilhouetteComparator(limit.beginAngle));
    	
    	Iterator <ShipSilhouette> itr = blockedAngles.iterator();
		
    	Arc earlier = null, currentBlocker = null;
    	
    	// getBlockingSilhuettes returns only silhouettes that are at least partially in our turret's targeting arc
    	while (itr.hasNext()) {
    		currentBlocker = itr.next().fromTurret;
    		if (earlier != null && earlier.contains(currentBlocker)) {
    			// if the earlier arc contains this arc there's no need to process this arc at all
    			continue;
    			// thus is guaranteed:
    			//  - arc[i].beginning >= arc[i-1].beginning (because of sorting)
    			//  - arc[i].end > arc[i-1].end (because of testing with the earlier reference)
    		}
    		earlier = currentBlocker;
    		
    		if (currentBlocker.contains(limit)) {
    			// we've covered the whole firing arc, no need to continue the loop
    			break;
    		}
    		if (currentBlocker.contains(limit.beginAngle)) {
    			limit.beginAngle = currentBlocker.endAngle;
    		}
    		else
    		{
    			// there's a hole in the covered angles
    			// from currentBeginAngle to currentBlocker.beginAngle
    			anglesToTarget.add(new Arc(limit.beginAngle, currentBlocker.beginAngle));
    			//limit.beginAngle = currentBlocker.beginAngle;
    			limit.beginAngle = currentBlocker.endAngle;
    		}
    	}
    	
    	// check if we blocked the target fully
    	if (currentBlocker != null && currentBlocker.contains(limit) == false)
    	{
    		// there was 
    		anglesToTarget.add(new Arc(limit));
    	}
    	
    	// compress continuous angles in separate arcs to single arcs
    	return Visibility.combineContinousArcs(anglesToTarget);
	}
	
	
	/**
	 * Returns all silhouettes that block partially or fully the target silhouette,
	 * i.e. silhouettes of all ships that are between the origin point and the target silhouette.  
	 * 
	 * Does NOT check if the silhouettes block other silhouettes.
	 * 
	 * @param target silhouette that is created from the target ship
	 * @param turret the point of origin we're doing the examining from
	 * @param shootingShip ship that is shooting, given so that a ship would not block it's own turrets
	 * @param minDistSq minimum distance to the target ship, squared
	 * @return a list of silhouettes that block the target silhouette
	 */
	public ArrayList<ShipSilhouette> getBlockingSilhuettes(ShipSilhouette target, Point2D.Double turret, Ship shootingShip, double minDistSq)
	{
		//logger.log(Level.INFO, "creating silhouettes from {0} ships", shipsRef.get().size());
		ArrayList<ShipSilhouette> blockedAngles = new ArrayList<ShipSilhouette> ();
		
		if (target == null) {
			logger.log(Level.INFO, "requested to create blocking silhouettes for null target");
			return blockedAngles;
		}
		
		Ship targetShip = target.getShip();
		
		// we form a triangle from the turret into the target silhouette
		// it is used in checking if any other silhouette blocks the target silhouette
		Line2D.Double triLeft = new Line2D.Double(turret, target.getBeginCorner());
		Line2D.Double triRight = new Line2D.Double(turret, target.getEndCorner());
		Line2D.Double triEnd = new Line2D.Double(target.getBeginCorner(), target.getEndCorner());
		Line2D blocker;
		
		Path2D.Double triangle = new Path2D.Double();
		triangle.moveTo(turret.x, turret.y);
		triangle.lineTo(target.getBeginCorner().x, target.getBeginCorner().y);
		triangle.lineTo(target.getEndCorner().x, target.getEndCorner().y);
		triangle.lineTo(turret.x, turret.y);
		
		boolean silhBlocks;
		
		Iterator itr = getShipIterator();
		
    	while (itr.hasNext()) {
    		Ship s = (Ship) itr.next();
    		if (s == null || s.equals(targetShip) || s.equals(shootingShip)) {
    			continue;
    		}
    		
    		ShipSilhouette p = Visibility.generateShipSilhouette(s, turret, target.fromTurret, minDistSq);
    		
    		if (p == null) {
    			// this ship isn't in the arc or is too far away
    			continue;
    		}
    		
    		// rest of the loop is for checking if the generated silhouette actually block our target or not
    		silhBlocks = false;
    		
    		blocker = p.getSilhLine();
    		
    		if (triLeft.intersectsLine(blocker) || triRight.intersectsLine(blocker) || triEnd.intersectsLine(blocker))
    		{
    			// candidate goes over one of the lines of the triangle, and thus blocks
    			silhBlocks = true;
    		}
    		else if (triangle.contains(blocker.getP1()) || triangle.contains(blocker.getP2()))
    		{
    			// the blocker is within the triangle, and thus blocks
    			silhBlocks = true;
    		}
    		
    		if (silhBlocks) {
    			blockedAngles.add(p);
    		}
    		
    	}
    	
    	return blockedAngles;
	}
	
	protected /*abstract*/ Iterator getShipIterator() {
		return null;
	}
}